typedef struct bistnode
{
    datatype data;
    struct bistnode *lchild, *rchild;
} BiSTNode, *BiSTree;
#pragma region 【算法6 - 5(a)】二叉排序树上的查找
BiSTNode *BST_Search1(BiSTree t, keytype kx)
{
    //在二叉排序树t上查找关键码为kx的元素，若找到，返回所在结点的地址，否则返回空指针 
    p = t;
    while (p) //从根结点开始查找
    {
        if (kx == p->data.key)
            return (p); // kx等于当前结点p的关键码，查找成功
        if (kx < p->data.key)
            p = p->lchild; // kx小于p的关键码转左子树查找
        else
            p = p->rchild; // kx大于p的关键码转右子树查找
    }
    return NULL; //查找失败
}
#pragma endregion
#pragma region 【算法6 - 5(b)】二叉排序树上的查找（递归）
BiSTNode *BST_Search2(BiSTree t, keytype kx)
{ //在二叉排序树t上查找关键码为kx的元素，若找到，返回所在结点的地址，否则返回空指针
    if (t == NULL || t->data.key == kx)
        return (t); //若树空，或者根结点的关键码等于kx，返回t
    else if (kx < t->data.key)
        BST_Search2(t->lchild, kx); // kx小于p的关键码在左子树查找
    else
        BST_Search2(t->rchild, kx); // kx大于p的关键码在右子树查找
}
#pragma endregion
#pragma region 【算法6 - 6】在二叉排序树中插入结点
BiSTree BST_InsertNode(BiSTree t, keytype kx)
{ //在二叉排序树上插入关键码为kx的结点
    BiSTNode *f, *p, *s;
    p = t;
    while (p) //寻找插入位置
    {
        if (kx == p->data.key)
        {
            printf("kx已存在,不需插入");
            return (t);
        }
        else
        {
            f = p; //结点f指向结点p的双亲
            if (kx < p->data.key)
                p = p->lchild;
            else
                p = p->rchild;
        }
    }
    s = (BiSTNode *)malloc(sizeof(BiSTNode)) ; //申请并填装结点
            s->data.key = kx;
    s->lchild = NULL;
    s->rchild = NULL;
    if (!t)
        t = s; //向空树中插入时F
    else if (kx < f->data.key)
        f->lchild = s; //插入结点s为结点f的右子
    else
        f->rchild = s; //插入结点s为结点f的左孩子
    return (t);
}
#pragma endregion
#pragma region 【算法6 - 7】构造一棵二叉排序树
BiSTree BST_ Creat() //生成二叉排序树
{
    BiSTree t = NULL;
    keytype kx;
    scanf("%d", &kx); //假设关键码是整型的
    scanf(…);         //读入其它信息
    while (kx != 0)   //假设读入0结束
    {
        t = BST_ InsertNode(t, kx); //向二叉排序树t中插入关键码为kx的结点
        scanf("%d", &kx);           //输入下一关键码*
        scanf（… ）;
    }
    return (t);
}
#pragma endregion
#pragma region 【算法6 - 8】二叉排序树上删除一个结点
BiSTree BST_ DeleteNode(BiSTree t, keytype kx)
{ //在二叉排序树t中删除关键码为kx的元素，返回数根指针
    BiSTNode *f, *p, *r, *s, *pres;
    // p指向待删结点，f指向*p的双亲，s指向* p的中序直接后继
    // pres是s的双亲
    p = t;
    f = NULL;
    while (p && p->data.key != kx) //查找该结点
    {
        f = p; // f指向结点*p的双亲
        if (kx < p->data.key)
            p = p->lchild;
        else
            p = p->rchild;
    }
    if (!p)
    {
        printf("kx不存在，不能删除！");
        ruturn t;
    }
    if (p->lchild && p->rchild)
    { //若待删结点既有左子树又有右子树
        pres = p;
        s = p->rchild;
        while (s->lchild) //在p的右子树上搜索最左下结点s
        {
            pres = s;
            s = s->lchild;
        }                  //即*s是*p的中序后继
        p->data = s->data; //用*s结点替代*p结点，待删除*s结点
        r = s->rchild;     // s的右子树上升
        if (pres == p)
            pres->rchild = r;
        else
            pres->lchild = r;
        free(s);
        return t;
    }
    else
    { //第(1)、(2)种情况：待删除结点是叶结点或单支结点
        if (p->rchild == NULL)
            r = p->lchild;
        else
            r = p->rchild;
        if (f == NULL)
        {
            free(p); //待删除结点是根结点
            return r;
        }
        else if (f->lchild == p)
            f->lchild = r else f->rchild = r;
        free(p);
        return t;
    }
    #pragma endregion